/*
 * Copyright 北京航空航天大学 @ 2015 版权所有
 */
package com.buaa.edu.leetcode.algorithm.hash;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * <p>
 * 单词拼接 输入字符串S和列表L，L是含有长度相同的单词，找出所有子串的开始下标，该子串由L的所有单词拼接而成，没有夹杂其它字符。 
 * s: "barfoothefoobarman" words:["foo", "bar"]
 * You should return the indices: [0,9].
 * 
 * </p>
 * 
 * @author towan
 * @email tongwenzide@163.com
 * @time 2015年5月25日
 */
public class SubstringWithConcatenationOfAllWord {

 public List<Integer> findSubstring(String s, String[] words) {
     List<Integer> result = new ArrayList<Integer>();
     int tokenLen = words[0].length();
     int tokenCount = words.length;
     int len = tokenLen*tokenCount ;
     
     //记录数组单词的情况
     Map<String,Integer> wordMap =  new HashMap<>();
     for(String str:words){
         if(wordMap.containsKey(str)){
             wordMap.put(str, wordMap.get(str)+1);
         }else{
             wordMap.put(str, 1);
         }
     }
     for(int i=0;i<s.length()-len+1;i++){
         //先取出相同长度的字符串
         String str = s.substring(i,i+len);
         int count = 0;
         Map<String,Integer> leftMap = new HashMap<>(wordMap);
         for(int j=0;j<tokenCount;j++){
             //读取每个单词
             String token = str.substring(j*tokenLen,(j+1)*tokenLen);
             if(!leftMap.containsKey(token)){
                 //不再目标数组中
                 break;
             }else{
                 //对应单词的频次减一，获得的单词量加1
                 leftMap.put(token, leftMap.get(token)-1);
                 if(leftMap.get(token)>=0){
                     count++;
                 }else{
                     break;
                 }
             }
         }
         if(count == tokenCount){
             result.add(i);
         }
     }
     
     return result;
    }
 public static void main(String[] args) {
    String s = "barfoothefoobarman";
    String words[] = {"foo","bar"};
    SubstringWithConcatenationOfAllWord concatenationOfAllWord = new SubstringWithConcatenationOfAllWord();
    System.out.println(concatenationOfAllWord.findSubstring(s, words));
}
}
